package sort;

public class ShellSort {
    /**
     * 希尔排序-也称之为缩小增量排序
     * 将一组数据分为n组 n/2组 n/4组，直至1组，分别对每组进行插入排序
     * 但说是分组，实际上是给定固定的间隔，在i++的同时 j步进固定的间隔，从而实现分组
     * 而且由于是固定的间隔，故有利于让小的元素往前，大的元素往后
     * */
    /**
     * 设置分组*/
    public void shellSort(int[] array) {
        int gap = array.length;
        while(gap>1) {
            gap/=2;
            shell(array,gap);
        }
    }

    /**
     * 对每组进行直接插入排序*/
    private void shell(int[] array, int gap) {
        for(int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            while(j>=0) {
                if(tmp<array[j]) {
                    array[j+gap] = array[j];
                    j-=gap;
                } else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

}
